{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "路线寻找成功！\n",
      "迷宫寻找出口路线：\n",
      "--> (1, 1)\n",
      "--> (1, 2)\n",
      "--> (2, 2)\n",
      "--> (2, 3)\n",
      "--> (3, 3)\n",
      "--> (3, 4)\n",
      "--> (4, 4)\n",
      "--> (5, 4)\n",
      "--> (5, 5)\n",
      "--> (4, 5)\n",
      "--> (4, 6)\n",
      "--> (5, 6)\n",
      "--> (6, 6)\n",
      "--> (6, 5)\n",
      "--> (6, 4)\n",
      "--> (7, 4)\n",
      "--> (7, 5)\n",
      "--> (7, 6)\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "'NoneType' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-33cae7203cee>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     83\u001b[0m                 \u001b[0mm\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     84\u001b[0m                 \u001b[1;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mopen\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 85\u001b[1;33m                     \u001b[1;32mif\u001b[0m  \u001b[0mGJ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mopen\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m<\u001b[0m  \u001b[0mGJ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mopen\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0my\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     86\u001b[0m                         \u001b[0mm\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0my\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     87\u001b[0m                 \u001b[1;32mif\u001b[0m \u001b[0mm\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-1-33cae7203cee>\u001b[0m in \u001b[0;36mGJ\u001b[1;34m(this)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mGJ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mthis\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;31m#估价函数计算 h(n) = A*B\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0mthis\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mthis\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mJudge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mthis\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mthis_copy\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mthis\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: 'NoneType' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "def GJ(this):#估价函数计算 h(n) = A*B\n",
    "    return this[0] * this[1]\n",
    "\n",
    "def Judge(this,p):\n",
    "    this_copy = this[:]\n",
    "    this_copy.insert(0,p)\n",
    "    for i in open:\n",
    "        for x in i:\n",
    "            if p == x:\n",
    "                return\n",
    "    for i in closed:\n",
    "        for x in i:\n",
    "            if p == x:\n",
    "                return\n",
    "    open.append(this_copy)\n",
    "    return\n",
    "\n",
    "def found(k,array):\n",
    "    for i in array:\n",
    "        if i[0:2]== k:\n",
    "            return i\n",
    "\n",
    "if  __name__ == '__main__':\n",
    "\n",
    "    M = [(1,1,0,1,0,0),(2,1,0,0,1,1),(3,1,0,0,1,0),(4,1,0,1,0,1),(5,1,0,0,1,0),(6,1,0,1,0,1,),(7,1,0,0,1,0),\n",
    "         (1,2,1,1,0,1),(2,2,0,1,1,1),(3,2,0,0,1,1),(4,2,1,1,1,0),(5,2,0,0,0,1),(6,2,1,1,1,1),(7,2,0,1,1,0),\n",
    "         (1,3,1,1,0,0),(2,3,1,1,0,1),(3,3,0,1,1,0),(4,3,1,0,0,1),(5,3,0,0,1,0),(6,3,1,1,0,0),(7,3,1,0,0,0),\n",
    "         (1,4,1,0,0,0),(2,4,1,1,0,0),(3,4,1,0,0,1),(4,4,0,0,1,1),(5,4,0,1,1,0),(6,4,1,1,0,1),(7,4,0,1,1,0),\n",
    "         (1,5,0,1,0,1),(2,5,1,1,1,0),(3,5,0,1,0,0),(4,5,0,1,0,1),(5,5,1,0,1,0),(6,5,1,1,0,0),(7,5,1,1,0,0),\n",
    "         (1,6,1,0,0,1),(2,6,0,0,1,1),(3,6,1,0,1,0),(4,6,1,0,0,1),(5,6,0,0,1,1),(6,6,1,0,1,0),(7,6,1,1,0,0)]\n",
    "\n",
    "    start = M[0]\n",
    "    end = M[-1]\n",
    "    open = []  #创建open表\n",
    "    closed = [] #创建closed表\n",
    "    open.append([start])\n",
    "    while(1):\n",
    "        if len(open) == 0:\n",
    "            print(\"未搜索到解！\")\n",
    "            break\n",
    "        else:\n",
    "            this = open.pop(0)\n",
    "            closed.append(this)\n",
    "            if this[0] == end:\n",
    "                print(\"路线寻找成功！\")\n",
    "                print('迷宫寻找出口路线：')\n",
    "                for i in this[::-1]:\n",
    "                    print('-->',i[0:2])\n",
    "                exit()\n",
    "\n",
    "        #扩展节点\n",
    "           #向上寻找\n",
    "            if this[0][2] == 1:\n",
    "                change1 = this[0][0]\n",
    "                change2 = this[0][1]-1\n",
    "                k = (change1,change2)\n",
    "                p = found(k,M)\n",
    "                Judge(this,p)\n",
    "            # 向下寻找\n",
    "            if this[0][3] == 1:\n",
    "                change1 = this[0][0]\n",
    "                change2 = this[0][1] + 1\n",
    "                k = (change1,change2)\n",
    "                p = found(k,M)\n",
    "                Judge(this,p)\n",
    "            # 向左寻找\n",
    "            if this[0][4] == 1:\n",
    "                change1 = this[0][0] - 1\n",
    "                change2 = this[0][1]\n",
    "                k = (change1,change2)\n",
    "                p = found(k,M)\n",
    "                Judge(this,p)\n",
    "            # 向右寻找\n",
    "            if this[0][5] == 1:\n",
    "                change1 = this[0][0] + 1\n",
    "                change2 = this[0][1]\n",
    "                k = (change1,change2)\n",
    "                p = found(k,M)\n",
    "                Judge(this,p)\n",
    "\n",
    "            #计算估计函数h(n) = A*B 重排open表\n",
    "            for x in range(0,len(open)-1):\n",
    "                m = x\n",
    "                for y in range(x+1,len(open)):\n",
    "                    if  GJ(open[x][0]) <  GJ(open[y][0]):\n",
    "                        m = y\n",
    "                if m != x:\n",
    "                    open[x],open[m] = open[m],open[x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
